1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to broadcast encryption (BE), and more particularly, to managing a key of a user for a BE.
2. Description of the Related Art
Mobile communication industry operators and contents providers desire to control and transmit their contents to consumers using a predetermined method. A method of controlling consumption and distribution of digital media objects is referred to as digital rights management (DRM).
Open Mobile Alliance (OMA), which is a consortium established on June 2002 by global enterprises related to wireless devices and services such as Nokia, Intel, Vodafone, Microsoft, and Samsung Electronics to develop the standards of compatible wireless services and expand wireless services thereof, has made efforts to standardize DRM systems.
However, the OMA fails to offer a security service for protecting data confidentiality and authenticating devices of subscribers, and for revoking the devices of the subscribers and other devices, as necessary.
BE is a method of effectively transmitting information only to all users of a transmitter, i.e., a broadcast center, desires to transmit and must be effectively used in a case of arbitrary and dynamic changes of a set of users who are to receive information. In the BE, revocation or exclusion of undesired users, for example, illegal or expired users is the most important.
FIG. 1 is a view illustrating a network structure of a data transmitting system using a general BE. Referring to FIG. 1, a contents producer 100 produces various types of data including audio and video data and provides the various types of data to a service provider 110.
The service provider 110 broadcasts the various types of data received from the contents producer 100 to authorized users having paid for corresponding data, for example, a mobile DRM network 140 and a smart home DRM network 150, via various wire and wireless communication networks.
In particular, the service provider 110 may transmit the various types of data to a device of users such as a set-top box 141 including various satellite receivers via a satellite 120, and also to a mobile terminal 142 via a mobile communication network. Also, the service provider 110 may transmit the various types of data to terminals 150 through 155 of the smart home DRM network 150.
Here, the data is encrypted by BE so that an illegal user 160, who does not pay for corresponding data, cannot use the data.
The stability of an encryption and decoding system generally depends on a system managing an encryption key. A method of deriving the encryption key is important to the system. In addition, it is important to manage and update the encryption key.
BE has been changed since its introduction in 1991 and supposes stateless receivers at the present time. The concept of the BE means that secret keys of individual users are not changed or updated at all with a change of a session.
Here, “k-resilient” is used for stability and means that k users of excluded users cannot restore information in spite of their conspiring attacks. The symbol r generally denotes a number of excluded users. Thus, “r-resilient” means that information is safe from conspiring attacks of all of the excluded users.
In BE, a transmission overhead, a storage overhead, and a computation overhead are important. The transmission overhead denotes an amount of a header to be transmitted by a transmitter, the storage overhead denotes an amount of encryption keys to be stored by a user, and the computation overhead denotes a computation amount necessary for obtaining a session key via a user.
In particular, it is a great task to reduce the transmission overhead. The transmission overhead was, in the past, proportional to a total number N of users but is proportional to a number r of excluded users at the present time. A reduction of the transmission overhead to be less than the number r of excluded users is a great task to the BE with the introduction of schemes to allow the transmission overhead to be proportional to the number r of excluded users.
Based on the problems of the BE, “Subset Difference (SD) Method” published by Naor-Naor-Lotspiech shows the best result among announced results. In the SD method, if a total number of users is n, a storage overhead of O(log1+en) and a transmission overhead of O (2r−1) are required.
However, the SD method cannot be used by a plurality of users in terms of efficiency.
As described above, since Berkovits first announced a paper on BE in 1991, various algorithms have been suggested. Secret sharing, a subset cover-free system model, a tree structure, and the like are important algorithms.
The secret sharing-based model was first suggested by S. Berkovits in 1991 and then improved in a paper entitled “Efficient Trace and Revoke Schemes” by M. Noar and B. Pinkas in 2000. In “How to Broadcast a Secret” by S. Berkovits, a polynomial interpolation method and a vector-based secret sharing method were suggested.
In the polynomial interpolation method, a center, i.e., a broadcast center or a transmitter, transmits points (xi, yi) to individual users via a secret channel. Here, xi varies, and (xi, yi) are secret keys of the individual users.
The center selects a polynomial P having a random integer j and a degree t+j+1 is selected to broadcast secret information S to t authorized users of each session. The polynomial P passes secret keys (xi, yi) of the t authorized users and j random points (x, y) and (O, S) that are not secret keys of other users.
The center transmits t+j points and other points on the polynomial P. The t authorized users know about a point (their own secret keys) besides the t+j points and thus can restore the polynomial P having the degree t+j+1 and obtain the secret information S. However, the excluded users know only about the t+j points and thus cannot restore the polynomial P.
In the polynomial interpolation method, a transmission overhead is O(t+j+1), a storage overhead is O(1), and a computation overhead is about t3 times. Also, revocation is easy, traitors can be prevented, and traitor tracing is possible. However, the polynomial interpolation method is inefficient for a large number of users. Also, in a case where the polynomial interpolation method is repeatedly used, the polynomial interpolation method is not safe. Thus, the polynomial interpolation method cannot be substantially used.
“Efficient Trace and Revoke Schemes” by M. Noar and B. Pinkas uses a threshold secret sharing method using a Lagrange's interpolation formula. In the method by Noar-Pinkas, r polynomial can be restored with r+1 points on the r polynomial, but not with r points.
In other words, the center selects a random t polynomial P and offers different points on the random t polynomial P to individual users. If r users are excluded, the center sums secret keys of the r users and randomly selected t-r points and then broadcasts information as to t points.
As a result, although the excluded users sum their secret information, they know only about the t points. Non-excluded users can know about t+1 points and thus restore the polynomial P. A session key value P(0) is obtained using the polynomial P.
In this method, revocation is easy, traitors can be prevented, and traitor tracking is possible. In particular, new users can be added, a transmission overhead is O(t), and a storage overhead is O(1). Thus, this method is considerably efficient.
However, in the case of this method, users more than t that are a first determined number cannot be excluded. In addition, a computation overhead necessary for computing a number of transmitted points or a polynomial depends on t. Thus, this method is inefficient in many cases. Moreover, as t becomes large, computation time is increased. Thus, it is difficult to use this method when a plurality of users are included.
In the subset cover-free system model, when a set of all users is S, a subset cover-free system is defined in a set whose members are subsets of the set S. If such a system is found, a BE can be performed using the system. However, a storage overhead and a transmission overhead are about O(r log n). Thus, the subset cover-free system model is inefficient.
Also, a method of expanding an l-resilient model into a k-resilient model was introduced. An 1-resilient scheme can be relatively easily invented. Thus, such an expansion appears meaningful. However, the efficiency of the 1-resilient scheme is greatly deteriorated during the expansion.
Methods using a tree structure have been recently noticed. C. K. Wong, M. Gouda, and G. S. Lam suggested a Logical-tree-hierarchy (LTH) in 1998. However, in the LTH, a large number of users cannot be excluded in a one-time session. Also, as a session goes by, secret keys of users are changed. Thus, the subset cover-free system model is distant from the BE supposing stateless receivers. Thereafter, D. Naor, M. Naor, and J. Lotspiech suggested “Complete Subset (CS) Cover Scheme” and “Subset Difference (SD) Scheme” in 2001.
On the supposition that a number of users is n and a number of excluded users is r in both methods, the center forms a binary tree having a height of log n and allots corresponding secret keys to all nodes. Also, the center allots users to leaf nodes one by one.
Describing the CS Cover scheme, each user receives secrete keys of all nodes positioned on a path from a root node to the user's leaf node from the center and stores the secrete keys. Here, a subtree not including excluded users is called a CS. If such CSs are appropriately collected, the CSs can include only non-excluded users.
Here, if a session key is encrypted with a secret key corresponding to a root node of used CSs and then transmitted, authorized users can restore the session key. However, since excluded users are not included in any CSs, the excluded users cannot restore the session key.
FIG. 2 is a view illustrating a BE allotting keys using a related art tree structure. Referring to FIG. 2, users 220 receiving data through a BE scheme have their own key values 32 through 47 and key values of nodes connected to them on a tree.
For example, a user 34 has his or her key value 34, a key value 209 of a node 17, a key value 204 of a node 8, a key value 202 of a node 4, and a key value 201 of a node 2. Here, the user 34 shares the key value 209 of the node 17 with a user 35. Also, users 32, 33, and 35 share the key value 204 of the node 8 with the user 34.
If the users 32 through 37 represent all authorized users, a header of data includes the key value 201 of the node 2 so that the key value 201 of the node 2 is equally transmitted to all of the authorized users. Thus, the data may be transmitted in security.
If a user having a key 221 of a user 36 is a revoked user, other users share key values of nodes related to the user 36. Thus, a process of updating the corresponding key values is required. In other words, key values 210, 205, 202, and 201 of the nodes 18, 9, 4, and 2 must be updated. Here, the key values are updated from a lower node to an upper node.
Since the user 37 shares the key value 210 of the node 18, an updated key value of the node 19 is encrypted as a key value of the user 37 and then transmitted to the user 37.
The user 37 and the users 38 and 39 under the node 19 share the key value 205 of the node 9. Thus, an updated key value of the node 9 is encrypted as the key value 210 of the node 18 that has been updated and then transmitted to the user 37, and the updated key value of the node 9 is encrypted as the key value 211 of the node 19 and then transmitted to the users 38 and 39.
The users 32, 33, 34, and 35 under the node 8 and the users 37, 38, and 39 under the node 9 share the key value 202 of the node 4. Thus, an updated key value of the node 4 is encrypted as the key value 204 of the node 8 and then transmitted to the users 32 through 35. Also, the updated key value of the node 4 is encrypted as the key value 205 of the node 9 and then transmitted to the users 37 through 39.
The users 32 through 39 under the node 4, except the user 36, and the users 40 through 47 under the node 5 share the key value 201 of the node 2. Thus, an updated key value of the node 2 is encrypted as the key value 202 of the node 4 that has been updated and then transmitted to the users 32, 33, 34, 35, 37, 38, and 39. Also, the updated key value of the node 2 is encrypted as the key value 203 of the node 5 and then transmitted to the users 40 through 47. Accesses of revoked users may be intercepted through such a key updating process.
In the above-described method, i.e., the CS model, a transmission overhead is O(r log(n/r)) that is a number of CSs including only non-excluded users, and a storage overhead is O(log n).
An SD model is a modification of the above-described CS model that requires a storage overhead of O(log2 n) and a transmission overhead of O(2r−1) so as to improve the transmission overhead. The SD model considers a subtree obtained by subtracting a subtree having a node w of a subtree, having a node v as a root node, as a root node from the corresponding substree. Leaf nodes under this subtree are authorized users, and leaf nodes under the subtree having the node w as the root node are excluded users.
If excluded users are put among an appropriate number of authorized users, the SD model may require a subset unlike the CD model requiring two or more subsets.
In the SD model, hash values of keys allotted to nodes from the node v to the node w are obtained, and then values corresponding to the hash values are determined as session keys. Each user has hash values of sibling nodes of each node on a path from the user's node to a leaf node as secret keys. Therefore, only authorized users can restore session keys due to the one-way nature of a hash function. Here, in the SD model, a transmission overhead is O(2r−1), a storage overhead is O(log2 n), and a computation overhead is O(log n).
An LSD model that is an improvement of the SD model was suggested in 2002. In the LSD model, a layer is used for each subtree to reduce a storage overhead to O(log3/2n). However, a transmission overhead doubles that of the SD model.
Among the above-described BE models, the LSD or SD model using a tree structure shows the best efficiency. However, in the cases of the LSD or SD model using the tree structure, the number of subsets necessary for broadcasting greatly depend on positions of users. Thus, the LSD or SD model cannot be improved.
Also, considerable cost is required to maintain and mend the tree structure. Thus, more efficient BE schemes are required instead of the above-described tree structure.
In addition, stateless receivers must be considered at the present time. The stateless receivers are able to record past transmission histories and are changed depending on the states of the past transmission histories. The stateless receivers must operate based a current transmission and an initial setting.